package com.leetcode.partition6;

import java.util.Arrays;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/9/14 8:23
 */
public class LC524通过删除字母匹配到字典里最长单词 {

    public static String findLongestWord(String s, List<String> dictionary) {
        return dynamicProgramming(s, dictionary);
    }

    public static void main(String[] args) {
        String s = "abpcplea";
        List<String> dictionary = Arrays.asList("ale", "apple", "monkey", "plea");
        System.out.println(findLongestWord(s, dictionary));
    }

    private static String dynamicProgramming(String s, List<String> dictionary) {
        //dp[i][j]表示从i位置开始，j字符在s中第一次出现的位置，因此需要反向遍历
        int[][] dp = new int[s.length() + 1][26];
        Arrays.fill(dp[s.length()], s.length());
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                dp[i][j] = s.charAt(i) == (char) ('a' + j) ? i : dp[i + 1][j];
            }
        }
        Arrays.stream(dp).forEach(item -> System.out.println(Arrays.toString(item)));

        String answer = "";
        for (String word : dictionary) {
            boolean match = true;
            int j = 0;
            for (int i = 0; i < word.length(); i++) {
                if (dp[j][word.charAt(i) - 'a'] == s.length()) {            //未匹配的都是s的长度
                    match = false;                      //当前从字典中遍历的单词已经不能匹配，直接跳出匹配
                    break;
                }
                j = dp[j][word.charAt(i) - 'a'] + 1;    //当前单词的当前字符匹配，继续匹配下一个字符
            }
            //检验当前答案是否是最终答案
            if (match && (word.length() > answer.length() || (word.length() == answer.length() && word.compareTo(answer) < 0))) {
                answer = word;
            }
        }
        return answer;
    }

    private static String doubleIndex(String s, List<String> dictionary) {
        dictionary.sort((o1, o2) -> o1.length() == o2.length() ? o1.compareTo(o2) : o2.length() - o1.length());
        String answer = "";
        for (String word : dictionary) {
            int i = 0, j = 0;
            //检测word是否是s的子序列
            while (i < s.length() && j < word.length()) {
                if (s.charAt(i) == word.charAt(j)) j++;
                i++;
            }
            if (j == word.length()) {
                if (word.length() > answer.length() || (answer.length() == word.length() && word.compareTo(answer) < 0)) {
                    answer = word;
                    break;
                }
            }
        }
        return answer;
    }
}
